package q77_combine;

import java.util.ArrayList;
import java.util.List;

public class Solution_1 {
    List<List<Integer>> res;
    List<Integer> bin;
    public List<List<Integer>> combine(int n, int k) {
        res = new ArrayList<>();
        bin = new ArrayList<>();
        backtracking(n, k, 1);
        return res;
    }

    // 用标准的回溯模板尝试
    void backtracking(int n, int k, int cur) {
        // 剪枝——额外步骤
        if (bin.size() + (n - cur + 1) < k){
            return;
        }

        // 终止条件
        if (bin.size() == k) {
            res.add(new ArrayList<>(bin));
            return;
        }
        // 回溯
        for (int i = cur; i <= n; i++) {
            bin.add(i);
            backtracking(n, k, i + 1);
            bin.remove(bin.size() - 1);
        }

    }

}
